package Sort.sort2016;

public class QuickSort {

	public static void main(String[] args) {
		int[] array={9,7,8,6,5,4,3,2,1};
		quickSort(array);
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]);
		}
	}
	public static void quickSort(int[] array){
		if(array==null||array.length==0){
			return;
		}
		quickSort(array,0,array.length-1);
	}
	public static void quickSort(int[] array,int low,int high){
		if(low>=high){
			return;
		}
		int pos = partition(array,low,high);
		quickSort(array,low,pos-1);
		quickSort(array,pos+1,high);
	}
	public static int partition(int[] array,int low,int high){
		int key = array[low];
		while(low<high){
			while(low<high&&array[high]>=key){
				high--;
			}
			array[low]=array[high];
			while(low<high&&array[low]<=key){
				low++;
			}
			array[high]=array[low];
		}
		array[high]=key;
		return high;
	}

}
